/*
 * vim:foldmethod=marker:
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

struct deq {
	int *data;
	int head;
	int size;
	int nmemb;
};

void
deq_init_(struct deq *d, const int nmemb)
{
	d->nmemb = nmemb;
	d->data = malloc((size_t) nmemb * sizeof (*d->data));
	d->size = 0;
	d->head = 0;
}

int
deq_prepend(struct deq *d, int val)
{
	if (d->size < d->nmemb) {
		if (d->head == 0)
			d->head = d->nmemb-1;
		else
			--d->head;
		d->data[d->head] = val;
		d->size++;
		return 0; /* OK */
	} else {
		return 1; /* deq overflow */
	}
}

int
deq_append(struct deq *d, int val)
{
	if (d->size < d->nmemb) {
		d->data[(d->head + d->size) % d->nmemb] = val;
		++d->size;
		return 0;
	} else {
		return 1; /* deq overflow */
	}
}

int
deq_extract_first(struct deq *d)
{
	if (d->size > 0) {
		--d->size;
		if (d->head == d->nmemb)
			d->head = 0;
		return d->data[d->head++ % d->nmemb];
	} else {
		return 0; /* do not touch head and size */
	}
}

int
deq_extract_last(struct deq *d)
{
	return d->size ? d->data[(d->head + (--d->size)) % d->nmemb] : 0;
}

int
deq_first(const struct deq * d)
{
	return d->data[d->head];
}

int
deq_last(const struct deq * d)
{
	return d->data[(d->head + d->size - 1) % d->nmemb];
}

bool
deq_isempty(const struct deq *d)
{
	return d->size ? false : true;
}

int
deq_kill_(struct deq *d)
{
	if (d->nmemb > 0 && d->data != NULL) {
		free(d->data);
		d->nmemb = 0;
		d->head = 0;
		d->size = 0;
		return 0; /* ok */
	} else {
		return 1; /* deq is either not init'd or already free'd */
	}
}

int
main(int argc, char **argv)
{
	struct deq bookshelf;
	int side, book_id;

	deq_init_(&bookshelf, 10000);

	while (1) {
		scanf("%d", &side);

		if (side == 1) {
			scanf("%d", &book_id);
			deq_prepend(&bookshelf, book_id);
		} else if (side == 2) {
			scanf("%d", &book_id);
			deq_append(&bookshelf, book_id);
		} else if (side == 3) {
			printf("%d\n", deq_extract_first(&bookshelf));
		} else if (side == 4) {
			printf("%d\n", deq_extract_last(&bookshelf));
		} else if (side == 0) {
			break;
		} else {
			fprintf(stderr, "%s has encountered an unexpected error\n", argv[0]);
		}
	}

	deq_kill_(&bookshelf);

	return 0;
}
